#include <iostream>
#include <vector>
#include <algorithm>
#include<queue>
#include <string>
using namespace std;

/**
 * @brief 使用优先队列合并n个升序链表为一个升序链表
 */

//  Definition for singly-linked list.
struct ListNode {
    int val;
    ListNode *next;
    ListNode() : val(0), next(nullptr) {}
    ListNode(int x) : val(x), next(nullptr) {}
    ListNode(int x, ListNode *next) : val(x), next(next) {}
};

struct cmp{
    bool operator()(const ListNode* v1,const ListNode* v2){
        return v1->val > v2->val;
    }
};

class Solution {
public:
    ListNode* mergeKLists(vector<ListNode*>& lists) {
        priority_queue<ListNode*,vector<ListNode*>,cmp> pq;
        for(int i=0;i<lists.size();i++){
            // 若为空就没必要加入到链表之中
            if(lists[i] != nullptr){
                pq.push(lists[i]);
            }
        }
        ListNode* head = nullptr;
        ListNode* cur;
        while(!pq.empty()){
            ListNode* tmp = pq.top();
            ListNode* newNode = new ListNode(tmp->val);
            if(head==nullptr){
                head = newNode;
                cur = head;
            } else {
                 cur->next = newNode;
                cur = cur->next;
            }
            pq.pop();
            if(tmp->next){
                tmp = tmp->next;
                pq.push(tmp);
            }
        }
        return head;
    }
};

int main()
{
    Solution solution;
    vector<ListNode*> input;
    vector<vector<int>> vecList = {{1,4,5},{1,3,4},{2,6}}; 
    for(int i=0;i<vecList.size();i++){
        ListNode* head = nullptr;
        ListNode* cur = nullptr;
        for(int j=0;j<vecList[i].size();j++){
            ListNode* tmp = new ListNode(vecList[i][j]);
            if(head==nullptr){
                head = tmp;
                cur = head;
            } else {
                cur->next = tmp;
                cur = cur->next;
            }
        }
        input.push_back(head);
    }
    ListNode* ans=solution.mergeKLists(input);

    return 0;
}